1. Field of the Present Methods and Devices
The present methods and devices relate generally to the fields of labeling and matching. More particular, they relate to labeling graphical representations of trees, such as automated anatomical labeling of human airway trees. They also relate to matching corresponding points of at least two graphical representations, such as automated matching of corresponding branch-points of at least two graphical representations of a tree, such as a human airway tree.
2. Description of Related Art
Lung diseases like lung cancer, emphysema, and cystic fibrosis are a significant cause of disability and premature death in western countries. In North America, for example, fatalities from lung cancer outnumber those from colon, breast, and prostate cancer combined.
Lung imaging plays a crucial role in the diagnosis, study, and treatment of lung disorders as well as in physiological studies concerned with pulmonary functionality. Modern multidetector-row CT scanners (MDCT) provide a wealth of information. Volumetric lung images of the size of several hundred MBytes are not uncommon. The manual analysis of these images is often time-consuming, tedious, and error prone. And with the high volume of scans taken, manual analysis is in many cases not economical.
The quantitative assessment of intrathoracic airway trees is important for the objective evaluation of the bronchial tree structure and function. Functional understanding of pulmonary anatomy as well as the natural course of respiratory diseases like asthma, emphysema, cystic fibrosis, and many others is limited by our inability to repeatedly evaluate the same region of the lungs time after time and perform accurate and reliable positionally corresponding measurements.
Branch-point matching and anatomical labeling are both tedious and error-prone to perform manually. Working with human in-vivo data poses challenges. In-vivo trees deviate from ideal trees because of anatomical variations and because of false-branches introduced by imperfections in the preceding segmentation and skeletonization processes.
Few attempts at automating the branch-point matching process have been made. Pisupati et al. (1996a) and Pisupati et al. (1996b) presented a matching algorithm based on dynamic programming, which was only applied to very similar pairs of canine trees. Pisupati et al. stated that they expect the method to fail on human in-vivo scans. Park (2002) presented a tree-matching method based on an association graph (Pelillo et al. (1999)), but his method was applied only to phantom data and does not tolerate false branches.
Publications about automated anatomical labeling are similarly sparse. Mori et al. (2000) presented a knowledge-based labeling algorithm. The proposed algorithm was only applied to incomplete trees (about 30 branches per tree), and the built-in knowledge base did not incorporate anatomical variations. Additionally, the algorithm is sensitive to missing and added (false) branches. Kitaoka et al. (2002) developed a branch-point labeling algorithm that uses a mathematical phantom as reference. Labels are assigned by matching the target tree against this phantom. The method cannot automatically handle false branches—they have to be pruned manually in a preprocessing step.
Other disclosures concerning an earlier version of the present labeling methods are described in Tschirren et al. (2003), Tschirren et al. (2002a) and Tschirren et al. (2002b).